package com.njupt.DynamicProgramming;


import com.njupt.Tree.Npreorder;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/23 19:08
 * @Description: 123. 买卖股票的最佳时机 III
 * 最多可以买卖两次
 * @Version: 1.0
 */


public class MaxProfit3_123 {

    public int maxProfit1(int[] prices) {
        int time_count = 2;
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0 - prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < len; i++) {
            if (time_count > 0) {
                if (dp[i - 1][1] - prices[i] > dp[i - 1][0]) {
                    dp[i][0] = dp[i - 1][1] - prices[i];
                    time_count--;
                } else {
                    dp[i][0] = dp[i - 1][0];
                }
                if (dp[i - 1][0] + prices[i] > dp[i - 1][1]) {
                    dp[i][1] = dp[i - 1][0] + prices[i];
                } else {
                    dp[i][1] = dp[i - 1][1];
                }
            } else {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1];
            }
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }

    /**
     * dp[i][0] 表示不操作
     * dp[i][1] 表示第一次持有股票的最大利润
     * dp[i][2] 表示第一次不持有股票的最大利润
     * dp[i][3] 表示第二次持有股票的最大利润
     * dp[i][4] 表示第二次不持有股票的最大利润
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][5];
        dp[0][0] = 0;
        dp[0][1] = 0 - prices[0];
        dp[0][2] = 0;
        dp[0][3] = 0- prices[0];
        dp[0][4] = 0 ;

        for (int i = 1; i < len; i++) {
            dp[i][0] = dp[i-1][0];
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]); //第i天第一次持有股票的最大利润，第i天买还是不买，不买就是之前就持有了，买就是当前才持有
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1] + prices[i]); //第i天第一次不持有股票的最大利润，第i天卖还是不卖，不卖就是之前就卖掉了，卖就是当前卖掉（在之前第一次持有股票的基础上 卖出）
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2] - prices[i]); //第i天第二次持有股票的最大利润，第i天买还是不买，不买就是之前就持有了，买就是当天就持有（在第一次卖出股票的基础上） 买入
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3] + prices[i]);

        }
        return dp[len-1][4];
    }

    public static void main(String[] args) {
        int[] prices = {3,3,5,0,0,3,1,4};
        MaxProfit3_123 test = new MaxProfit3_123();
        System.out.println(test.maxProfit(prices));
    }
}
